package 力扣.动态规划.区间DP.背包问题;


import java.util.Arrays;

public class bag01 {
    public static void main(String[] args) {
        int[] wights={2,3,4,5};//每个物品的体积
        int[] values={3,4,5,6};//每个物品的价值
        int[][] dp = bag01(4, 8, wights, values);
        //打印dp数组
        for (int i = 1; i <=4 ; i++) {
            for (int j = 1; j <=8 ; j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        int[] item=new int[4];
        //寻找最优价值的物品组成
        findWhat(4, 8, wights, dp, item);
        //打印item数组
        System.out.println(Arrays.toString(item));

        //一维法求背包问题
        int[] dp2= bag02(4, 10, values, wights);
        System.out.println(Arrays.toString(dp2));
    }
    /**
     * 基础版的01背包（二维法）
     * @param n 物品个数
     * @param maxWight 背包总容量
     * @param wights 每个物品的体积
     * @param values 每个物品的价值
     */
    static int[][] bag01(int n,int maxWight,int[]wights,int[]values){
        int[][] dp=new int[n+1][maxWight+1];
        for (int i = 1; i <=n ; i++) {
            int w=wights[i-1];
            int v=values[i-1];
            for (int j = 1; j <=maxWight; j++) {
                if (j>=w){
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w]+v);
                }else {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp;
    }
    /**
     * 进阶版01背包（一维法）
     * @param n
     * @param maxWeight
     * @param values
     * @param weight
     * @return
     */
    static int[] bag02(int n,int maxWeight,int[]values,int[]weight){
        int[] dp=new int[maxWeight+1];
        for (int i = 1; i <=n ; i++) {
            int w=weight[i-1];
            int v=values[i-1];
            for (int j =maxWeight ; j >=1 ; j--) {
                if (j>=w){
                    dp[j]=Math.max(dp[j],dp[j-w]+v);
                }
            }
        }
        return dp;
    }

    /**
     * 寻找最优解的物品构成
     * @param i 为物品个数
     * @param j 为背包的总容量
     * 其实只需传入 i,j即可
     */
    static void findWhat(int i ,int j,int[]wights,int[][] dp,int[]item){
        if (i>0) {
            int w = wights[i - 1];
            if (dp[i][j] == dp[i - 1][j]) {
                item[i - 1] = 0;
                findWhat(i - 1, j, wights, dp, item);
            } else  {
                item[i - 1] = 1;
                findWhat(i - 1, j - w, wights, dp, item);
            }
        }
    }


}
